﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace ProjectEulerIssues
{
	public class GoogleCodeJam_Africa2010_Qualification
	{
		public static void B_ReverseWords()
		{
			string[] data = File.ReadAllLines("b-large-practice.in");
			List<string> outF = new List<string>();
			for (int i = 1; i < data.Length; i++)
			{
				var s = string.Join(" ", data[i].Split(' ').Reverse());
				outF.Add("Case #" + i.ToString() + ": " + s);
			}
			File.WriteAllLines("b.out", outF.ToArray());
		}

		public static void C_T9Spelling()
		{
			var groups = new Dictionary<char, int>();
			var group_pos = new Dictionary<char, int>();
			var counter = 0;
			for (var c = 'a'; c <= 'r'; c++)
			{
				groups.Add(c, counter / 3 + 2);
				group_pos.Add(c, counter % 3 + 1);
				counter++;
			}
			groups.Add('s', 7);
			group_pos.Add('s', 4);
			groups.Add('t', 8);
			group_pos.Add('t', 1);
			groups.Add('u', 8);
			group_pos.Add('u', 2);
			groups.Add('v', 8);
			group_pos.Add('v', 3);
			groups.Add('w', 9);
			group_pos.Add('w', 1);
			groups.Add('x', 9);
			group_pos.Add('x', 2);
			groups.Add('y', 9);
			group_pos.Add('y', 3);
			groups.Add('z', 9);
			group_pos.Add('z', 4);
			groups.Add(' ', 0);
			group_pos.Add(' ', 1);
			string[] data = File.ReadAllLines("C-large-practice.in");
			List<string> outF = new List<string>();
			for (int i = 1; i < data.Length; i++)
			{
				var prev = 'A';
				var localAns = new StringBuilder();
				for (int j = 0; j < data[i].Length; j++)
				{
					var newC = data[i][j];
					if (prev == newC || (groups.ContainsKey(prev) && groups[prev] == groups[newC]))
					{
						localAns.Append(" ");
					}
					var newV = "";
					for (int j2 = 0; j2 < group_pos[newC]; j2++)
					{
						newV += groups[newC];
					}
					localAns.Append(newV);
					prev = newC;
				}
				outF.Add("Case #" + i.ToString() + ": " + localAns.ToString());
			}
			File.WriteAllLines("c.out", outF.ToArray());
		}
	}

	public class GoogleCodeJam_2008_Round1A
	{
		public static void A_MinimumScalarProduct()
		{
			string[] data = File.ReadAllLines("a-large-practice.in");
			var outF = new List<string>();
			int T = int.Parse(data[0]);
			for (int i = 1; i <= T; i++)
			{
				var v1 = data[(i - 1) * 3 + 2].Split(' ').Select(s => long.Parse(s)).ToList();
				var v2 = data[(i - 1) * 3 + 3].Split(' ').Select(s => long.Parse(s)).ToList();
				v1.Sort();
				v2.Sort((x1, x2) => { return (x1 == x2 ? 0 : x1 < x2 ? 1 : -1); });
				long sum = 0;
				for (int j = 0; j < v1.Count; j++)
				{
					sum += v1[j] * v2[j];
				}
				outF.Add("Case #" + i.ToString() + ": " + sum.ToString());
			}
			File.WriteAllLines("a.out", outF.ToArray());
		}

		public static void C_Numbers()
		{
			string[] data = File.ReadAllLines("c-small-practice (3).in");
			var outF = new List<string>();
			//(a1+b1)*(a2+b2)=a1*a2+(a1*b2+b1*a2)+b1*b2
			for (int i = 1; i < data.Length; i++)
			{
				long N = long.Parse(data[i]);
				long x = 3;
				long y = 1;
				for (long j = 2; j <= N; j++)
				{
					long x1 = x * 3 + 5 * y * 1;
					long y1 = x * 1 + y * 3;
					if (x1 > 10000 && y1 > 10000)
					{
						x = x1 % 1000;
						y = y1 % 1000;
					}
					else
					{
						x = x1;
						y = y1;
					}
				}
				double res = Math.Truncate(x + y * Math.Sqrt(5));
				if (res > 1000)
				{
					res = res % 1000;
				}
				string res_s = res.ToString();
				while (res_s.Length < 3)
				{
					res_s = "0" + res_s;
				}
				outF.Add("Case #" + i.ToString() + ": " + res_s);
			}
			File.WriteAllLines("c3_2.out", outF);
		}

		public static void C_Numbers_Python()
		{
			/*
			 def matrix_mult(A, B):
			  C = [[0, 0], [0, 0]]
			  for i in range(2):
				for j in range(2):
				  for k in range(2):
					C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % 1000
			  return C

			def fast_exponentiation(A, n):
			  if n == 1:
				return A
			  else:
				if n % 2 == 0:
				  A1 = fast_exponentiation(A, n/2)
				  return matrix_mult(A1, A1)
				else:
				  return matrix_mult(A, fast_exponentiation(A, n - 1))

			def solve(n):
			  A = [[3, 5], [1, 3]]
			  A_n = fast_exponentiation(A, n)
			 return (2 * M_n[0][0] + 999) % 1000
			 */

			Func<int[,], int[,], int[,]> matrix_mult = (int[,] A, int[,] B) =>
			{
				var C = new int[2, 2];
				for (int i = 0; i < 2; i++)
				{
					for (int j = 0; j < 2; j++)
					{
						for (int k = 0; k < 2; k++)
						{
							C[i, k] = (C[i, k] + A[i, j] * B[j, k]) % 1000;
						}
					}
				}
				return C;
			};

			Func<int[,], int, int[,]> fast_exponential = null;
			fast_exponential = (int[,] A, int n) =>
			{
				if (n == 1)
				{
					return A;
				}
				if (n % 2 == 0)
				{
					var A1 = fast_exponential(A, n / 2);
					return matrix_mult(A1, A1);
				}
				return matrix_mult(A, fast_exponential(A, n - 1));
			};

			Func<int, int> solve = (int n) =>
			{
				var A = new int[2, 2] { { 3, 5 }, { 1, 3 } };
				var A_n = fast_exponential(A, n);
				return (2 * A_n[0, 0] + 999) % 1000;
			};

			string[] data = File.ReadAllLines("c-large-practice (1).in");
			var outF = new List<string>();
			//(a1+b1)*(a2+b2)=a1*a2+(a1*b2+b1*a2)+b1*b2
			for (int i = 1; i < data.Length; i++)
			{
				int N = int.Parse(data[i]);
				string res_s = solve(N).ToString();
				while (res_s.Length < 3)
				{
					res_s = "0" + res_s;
				}
				outF.Add("Case #" + i.ToString() + ": " + res_s);
			}
			File.WriteAllLines("c3_3.out", outF);
		}
	}

	public class GoogleCodeJam_2010_Round1C
	{
		public static void A_RopeIntranet()
		{
			var data = File.ReadAllLines("a-large-practice (1).in");
			var outF = new List<string>();
			int N = int.Parse(data[0]);
			var caseNumber = 1;
			for (int i = 1; i < data.Length; i++)
			{
				var count = 0;
				int T = int.Parse(data[i]);
				var p1 = new List<int>();
				var p2 = new List<int>();
				for (int j = i + 1; j < i + 1 + T; j++)
				{
					int newp1 = int.Parse(data[j].Split(' ')[0]);
					int newp2 = int.Parse(data[j].Split(' ')[1]);
					for (int j2 = 0; j2 < p1.Count; j2++)
					{
						if ((p1[j2] < newp1 && p2[j2] > newp2) || (p1[j2] > newp1 && p2[j2] < newp2))
						{
							count++;
						}
					}
					p1.Add(newp1);
					p2.Add(newp2);
				}
				outF.Add("Case #" + caseNumber.ToString() + ": " + count.ToString());
				i += T;
				caseNumber++;
			}
			File.WriteAllLines("a.out", outF);
		}

		public static void B_LoadTesting()
		{
			var data = File.ReadAllLines("b-large-practice (1).in");
			var outF = new List<string>();
			for (int i = 1; i < data.Length; i++)
			{
				long L = long.Parse(data[i].Split(' ')[0]);
				long P = long.Parse(data[i].Split(' ')[1]);
				long C = long.Parse(data[i].Split(' ')[2]);
				var counter = 0;
				if (L * C < P)
				{
					long c1 = C;
					while (L * c1 < P)
					{
						counter++;
						c1 *= c1;
					}
				}
				outF.Add("Case #" + i.ToString() + ": " + counter.ToString());
			}
			File.WriteAllLines("b.out", outF);
		}
	}
}
